package com.fw.leetcode.doublepointer;

import com.fw.leetcode.LeetCode;

/**
 * 125. Valid Palindrome
 *
 * A phrase is a palindrome if, after converting all uppercase letters into lowercase letters
 * and removing all non-alphanumeric characters, it reads the same forward and backward.
 * Alphanumeric characters include letters and numbers.
 *
 * Given a string s, return true if it is a palindrome, or false otherwise.
 *
 * Example 1:
 *  Input: s = "A man, a plan, a canal: Panama"
 *  Output: true
 *  Explanation: "amanaplanacanalpanama" is a palindrome.
 *
 * Example 2:
 *  Input: s = "race a car"
 *  Output: false
 *  Explanation: "raceacar" is not a palindrome.
 *
 * Example 3:
 *  Input: s = " "
 *  Output: true
 *  Explanation: s is an empty string "" after removing non-alphanumeric characters.
 *               Since an empty string reads the same forward and backward, it is a palindrome.
 *
 * Constraints:
 *  1 <= s.length <= 2 * 10^5
 *  s consists only of printable ASCII characters.
 */
public class Num_0125 implements LeetCode {
    private interface Solution {
        boolean isPalindrome(String s);

        default void assertEquals(String s, boolean expected) {
            if (isPalindrome(s) != expected) {
                isPalindrome(s);
            }
        }
    }

    private static class MyFreqSolution implements Solution {

        @Override
        public boolean isPalindrome(String s) { // 最优：双指针（原位比较）：时O(n) 空O(1)
            /*
             * 验证回文串
             * - 在删除非英文字符后，同时转大写字母为小写字母 [a-zA-Z0-9]，验证是否回文串（不能更改相对位置）
             *
             * 特例：'P' - '0' = 32
             * - 不能简单用 'a' - 'A' = 32 判断大小写是否相等
             */
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                boolean compare = true;
                char leftCh = parseAzNum(s.charAt(left));
                char rightCh = parseAzNum(s.charAt(right));
                if (leftCh == '#') {
                    left++;
                    compare = false;
                }
                if (rightCh == '#') {
                    right--;
                    compare = false;
                }
                if (compare) {
                    if (leftCh != rightCh) {
                        return false;
                    }
                    left++;
                    right--;
                }
            }
            return true;
        }

        private char parseAzNum(char ch) {
            if (ch >= 'a' && ch <= 'z') {
                return ch;
            } else if (ch >= 'A' && ch <= 'Z') {
                return (char)(ch - 'A' + 'a'); // 字母大写转小写
            } else if (ch >= '0' && ch <= '9') {
                return ch;
            } else {
                return '#'; // 非法
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyFreqSolution();
        solution.assertEquals("A man, a plan, a canal: Panama", true);
        solution.assertEquals("race a car", false);
        solution.assertEquals(" ", true);
        solution.assertEquals("0P", false);
        solution.assertEquals("abb", false);
    }
}
